/*
 * adjacencia.cpp
 *
 *  Created on: 30/06/2011
 *      Author: george
 */

#include "adjacencia.h"
#include "adjnode.h"

#include <iostream>

Adjacencia::Adjacencia() {
	nullNode = new Adjnode();
	nullNode->peer = new Peer;
	nullNode->left = nullNode->right = nullNode;
	root = nullNode;
}

void Adjacencia::rotateWithLeftChild(Adjnode *&tree){
	Adjnode *aux = tree->left;
	tree->left = aux->right;
	aux->right = tree;
	tree = aux;
}

void Adjacencia::rotateWithRightChild(Adjnode *&tree){
	Adjnode *aux = tree->right;
	tree->right = aux->left;
	aux->left = tree;
	tree = aux;
}

void Adjacencia::splay(const Peer &peer, Adjnode *&tree){

//	Arvores esquerda e direita para o top-down splay
	Adjnode *leftTreeMax, *rightTreeMin;

//	Arvore central (raiz)
	static Adjnode header;

//	Inicia as arvores de esquerda e direita do da arvore central com o no sentinela
	header.left = header.right = nullNode;

//	Faz o mesmo com as arvores na esquerda e direita
	leftTreeMax = rightTreeMin = &header;

//	Garante que sempre havera combinacao
	*nullNode->peer = peer;

//	Realiza o splay top-down na arvore
	for(;;){

//		Se o valor no qual estamos realizando o splay for menor, verificaremos as subarvores esquerdas do root
		if( peer < *tree->peer){
//		Caso a o elemento da esquerda seja maior que o que queremos inserir, realizamos uma rotação
			if ( peer < *tree->left->peer){
				rotateWithLeftChild(tree);
			}
//		Chegamos ao fim da arvore
			if ( tree->left == nullNode ){
				break;
			}

//		Ligamos a arvore da esquerda
			rightTreeMin->left = tree;
			rightTreeMin = tree;
			tree = tree->left;

		}else if ( *tree->peer < peer ){

			if ( *tree->right->peer < peer ){
				rotateWithRightChild(tree);
			}

			if ( tree->right == nullNode ){
				break;
			}

			leftTreeMax->right = tree;
			leftTreeMax = tree;
			tree = tree->right;
		}else{
			break;
		}
	}

	leftTreeMax->right = tree->left;
	rightTreeMin->left = tree->right;

	tree->left = header.right;
	tree->right = header.left;
}


Session* Adjacencia::insert(Peer *info){
	static Adjnode *newNode = NULL;

	if ( newNode == NULL ){
		 newNode = new Adjnode(new Peer);
	}

	*newNode->peer = *info;

	if ( root == nullNode ){
		newNode->left = newNode->right = nullNode;
		root = newNode;

	}else{

		splay(*info, root);

		if ( *info == *root->peer ){
			throw DuplicatedPeerException();
		}

		if ( *info < *root->peer ){

			newNode->left = root->left;
			newNode->right = root;
			root->left = nullNode;
			root = newNode;
		}else if( *info > *root->peer){
			newNode->right = root->right;
			newNode->left = root;
			root->right = nullNode;
			root = newNode;
		}
	}

	newNode = NULL;

	return info->session;
}


bool Adjacencia::isEmpty(){
	return root == nullNode;
}

Adjnode *Adjacencia::find(Peer *info){

	splay(*info, root);
	if ( isEmpty() || *root->peer != *info ){
		return NULL;
	}

	return root;
}
